home *** CD-ROM | disk | FTP | other *** search
/ Clickx 115 / Clickx 115.iso / software / tools / windows / tails-i386-0.16.iso / live / filesystem.squashfs / usr / include / scribus-ng / desaxe / automata.h < prev    next >
Encoding:
C/C++ Source or Header  |  2007-02-17  |  6.9 KB  |  249 lines
  1. /*
  2.  *  automata.h
  3.  *  
  4.  *
  5.  *  Created by Andreas Vox on 02.06.06.
  6.  *  Copyright 2006 under GPL2. All rights reserved.
  7.  *
  8.  */
  9.  
  10.  
  11. #ifndef AUTOMATA_H
  12. #define AUTOMATA_H
  13.  
  14. #include <map>
  15. #include <set>
  16. #include <deque>
  17.  
  18. namespace automata {
  19.  
  20. template<class STATE, class INPUT, class OUTPUT>
  21. class FA_base {
  22. public:
  23.     FA_base(STATE s, OUTPUT d);
  24.     FA_base(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt);
  25.     virtual ~FA_base();
  26.  
  27.     typedef std::map<INPUT, OUTPUT> Transitions;
  28.  
  29.     const std::set<STATE>& states() const;
  30.     const std::set<INPUT>& inputs() const;
  31.     const Transitions& transitions(STATE s) const;
  32.     const STATE start() const;
  33.     const OUTPUT deflt() const;
  34.     const OUTPUT next(STATE from, INPUT input) const;
  35.     
  36.     void addState(STATE newState);
  37.     void addInput(INPUT newInput);
  38.     void setTransition(STATE from, INPUT input, OUTPUT to);
  39.  
  40. protected:
  41.     std::set<STATE> states_;
  42.     std::set<INPUT> inputs_;
  43.     std::map<STATE, Transitions> transitions_;
  44.     const Transitions noTransitions;
  45.     STATE start_;
  46.     OUTPUT default_;
  47. };
  48.  
  49. template<class STATE, class INPUT, class OUTPUT>
  50. FA_base<STATE, INPUT, OUTPUT>::FA_base(STATE s, OUTPUT d) : states_(), inputs_(), transitions_(), noTransitions(), start_(s), default_(d) 
  51. { 
  52.     states_.insert(s); 
  53. }
  54.  
  55. template<class STATE, class INPUT, class OUTPUT>
  56. FA_base<STATE, INPUT, OUTPUT>::FA_base(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt) : states_(states), inputs_(inputs), transitions_(), noTransitions(), start_(start), default_(deflt) 
  57. {
  58.     if (states_.find(start) == states_.end())
  59.         states_.insert(start);    
  60. }
  61.  
  62. template<class STATE, class INPUT, class OUTPUT>
  63. const std::set<STATE>& FA_base<STATE, INPUT, OUTPUT>::states() const 
  64. { 
  65.     return states_; 
  66. }
  67.  
  68. template<class STATE, class INPUT, class OUTPUT>
  69. const std::set<INPUT>& FA_base<STATE, INPUT, OUTPUT>::inputs() const 
  70. { 
  71.     return inputs_; 
  72. }
  73.  
  74. template<class STATE, class INPUT, class OUTPUT>
  75. const STATE FA_base<STATE, INPUT, OUTPUT>::start() const
  76. { 
  77.     return start_; 
  78. }
  79.  
  80. template<class STATE, class INPUT, class OUTPUT>
  81. const OUTPUT FA_base<STATE, INPUT, OUTPUT>::deflt() const
  82. { 
  83.     return default_; 
  84. }
  85.  
  86. template<class STATE, class INPUT>
  87. class DFA : public FA_base<STATE, INPUT, STATE> {
  88. public:
  89.     DFA(STATE s, STATE deflt): FA_base<STATE, INPUT, STATE>(s, deflt) {  }
  90.     DFA(const std::set<STATE>& states, const std::set<INPUT>& inputs, STATE start, STATE deflt)
  91.     : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
  92. };
  93.  
  94.  
  95. template<class STATE, class INPUT>
  96. class NFA : public FA_base<STATE, INPUT, std::set<STATE> > {
  97. public:
  98.     NFA(STATE s, std::set<STATE> d): FA_base<STATE, INPUT, std::set<STATE> >(s, d)  { }
  99.     NFA(std::set<STATE>& states, std::set<INPUT>& inputs, STATE start, std::set<STATE> deflt)
  100.     : FA_base<STATE, INPUT, STATE>(states, inputs, start, deflt) { }
  101.  
  102.     void addTransition(STATE from, INPUT input, STATE to);
  103.     
  104.     /*
  105.       NFA:  S x I -> P(S)
  106.       DFA':  P(S) x I -> P(S)
  107.       DFA:  N x I -> N
  108.      Algo:
  109.       todo = { NFA.start }
  110.       forall src in todo:
  111.          from = create(src)
  112.          ntrans: I -> P(S)
  113.          for all s in src
  114.            for all (i,t) in NFA.trans[s]:
  115.              ntrans[i] += t;
  116.          for all (i,nt) in ntrans:
  117.            n = create(nt);
  118.            if n is new:
  119.              DFA.addState(n);
  120.              todo += nt;
  121.            DFA.addTransition(from, i, n)
  122.      */
  123.     template<class NSTATE, class XXX>
  124.     DFA<NSTATE,INPUT>* constructDFA( XXX createState )
  125. //    DFA<NSTATE,INPUT>* constructDFA(NSTATE (*createState)( std::set<STATE> ))  // wont work
  126.     {
  127.         std::map<std::set<STATE>, NSTATE> newStates;
  128.     
  129.         std::set<STATE> startSet;
  130.         startSet.insert(FA_base<STATE,INPUT,std::set<STATE> >::start_);
  131.         NSTATE nstart = createState(startSet);
  132.         newStates[startSet] = nstart;
  133.  
  134.         NSTATE deflt = createState(FA_base<STATE,INPUT,std::set<STATE> >::default_);
  135.         newStates[FA_base<STATE,INPUT,std::set<STATE> >::default_] = deflt;
  136.         
  137.         DFA<NSTATE,INPUT>* result = new DFA<NSTATE,INPUT>(nstart, deflt);
  138.         result->addState(deflt);
  139.         
  140.         std::deque<std::set<STATE> > todo;
  141.         todo.push_back(startSet);
  142.         
  143.         while (todo.size() > 0)
  144.         {
  145.             const std::set<STATE> from = todo.front();
  146.             todo.pop_front();
  147.             std::map<INPUT,std::set<STATE> > ntrans;
  148.             // for all states in from
  149.             typename std::set<STATE>::const_iterator s_it;
  150.             typename std::map<INPUT, std::set<STATE> >::iterator tr_it;
  151.             for (s_it=from.begin(); s_it != from.end(); ++s_it)
  152.             {
  153.                 // for all transitions
  154.                 typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions& 
  155.                     trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[*s_it]);
  156.                 for (tr_it = trans.begin(); tr_it != trans.end(); ++tr_it)
  157.                 {
  158.                     ntrans[tr_it->first].insert(tr_it->second.begin(), tr_it->second.end());
  159.                 }
  160.             }
  161.             // construct new transitions
  162.             const NSTATE nfrom = newStates[from];
  163.             for (tr_it = ntrans.begin(); tr_it != ntrans.end(); ++tr_it)
  164.             {
  165.                 std::set<STATE> & state(tr_it->second);
  166.                 // create follow state
  167.                 NSTATE nstate;
  168.                 if ( newStates.find(state) == newStates.end() ) {
  169.                     nstate = createState(state);
  170.                     result->addState(nstate);
  171.                     newStates[state] = nstate;
  172.                     // remember follow state in todo if new
  173.                     todo.push_back(state);
  174.                 }
  175.                 else {
  176.                     nstate = newStates[state];
  177.                 }
  178.                 result->setTransition(nfrom, tr_it->first, nstate);
  179.             }
  180.         }
  181.         const std::set<INPUT>& inp(FA_base<STATE, INPUT, std::set<STATE> >::inputs());
  182.         typename std::set<INPUT>::const_iterator i;
  183.         for (i=inp.begin(); i != inp.end(); ++i)
  184.             result->addInput(*i);
  185.         return result;
  186.     }
  187. };
  188.  
  189.  
  190. template<class STATE, class INPUT, class OUTPUT>
  191. FA_base<STATE,INPUT,OUTPUT>::~FA_base() 
  192. {
  193.     // clean up
  194. }
  195.     
  196. template<class STATE, class INPUT, class OUTPUT>
  197. const typename FA_base<STATE,INPUT,OUTPUT>::Transitions& FA_base<STATE,INPUT,OUTPUT>::transitions(STATE s) const
  198. { 
  199.     typename std::map<STATE, Transitions>::const_iterator tr = transitions_.find(s);
  200.     if (tr != transitions_.end())
  201.         return tr->second;
  202.     else
  203.         return noTransitions; 
  204. }
  205.  
  206. template<class STATE, class INPUT, class OUTPUT>
  207. const OUTPUT FA_base<STATE,INPUT,OUTPUT>::next(STATE from, INPUT input) const
  208. {
  209.     const Transitions& tr(transitions(from));
  210.     typename Transitions::const_iterator it = tr.find(input);
  211.     return it==tr.end() ? default_ : it->second;
  212. }
  213.  
  214. template<class STATE, class INPUT, class OUTPUT>
  215. void FA_base<STATE,INPUT,OUTPUT>::addState(STATE newState)
  216. {
  217.     if (states_.find(newState) == states_.end())
  218.         states_.insert(newState);
  219. }
  220.  
  221.  
  222. template<class STATE, class INPUT, class OUTPUT>
  223. void FA_base<STATE,INPUT,OUTPUT>::addInput(INPUT newInput)
  224. {
  225.     if (inputs_.find(newInput) == inputs_.end())
  226.         inputs_.insert(newInput);
  227. }
  228.  
  229.  
  230. template<class STATE, class INPUT, class OUTPUT>
  231. void FA_base<STATE,INPUT,OUTPUT>::setTransition(STATE from, INPUT input, OUTPUT to)
  232. {
  233.     Transitions& trans(transitions_[from]);
  234.     trans[input] = to;
  235. }
  236.     
  237.  
  238. template<class STATE, class INPUT>
  239. void NFA<STATE, INPUT>::addTransition(STATE from, INPUT input, STATE to)
  240. {
  241.     typename FA_base<STATE,INPUT,std::set<STATE> >::Transitions & 
  242.         trans(FA_base<STATE,INPUT,std::set<STATE> >::transitions_[from]);
  243.     trans[input].insert(to);
  244. }
  245.  
  246. } // namespace
  247.  
  248. #endif
  249.